//猜数字大小 II
//测试链接：https://leetcode.cn/problems/guess-number-higher-or-lower-ii/
public class GetMoneyAmount {
    int[][] memo;
    public int getMoneyAmount(int n) {
        memo = new int[n+1][n+1];
        int ans = dfs(1,n);
        return ans;
    }

    public int dfs(int left, int right) {
        if(left >= right) return 0;
        if(memo[left][right] != 0 ) return memo[left][right];

        int max = 0;
        int min = Integer.MAX_VALUE;
        for(int i = left; i <= right; i++) {
            int n1 = dfs(left,i-1);
            int n2 =dfs(i+1,right);

            max = Math.max(n1, n2) + i;
            min = Math.min(min,max);
        }
        memo[left][right] = min;
        return min;
    }
}
